package pers.whj.util.set;

public class UFSet {
    private static final int DEFAULT_SIZE = 10;
    private int[] mParent;
    private int mSize;

    public UFSet(int size) {
        reset(size);
    }

    public int size() {
        return mSize;
    }

    public void reset(int size) {
        this.mSize = size > 0 ? size : DEFAULT_SIZE;
        mParent = new int[mSize];
        for (int i = 0; i < mSize; i++) {
            mParent[i] = -1;
        }
    }

    public int find(int x) {
        while (mParent[x] >= 0) {
            x = mParent[x];
        }
        return x;
    }

    public int collapsingFind(int x) {
        int j = x;
        while (mParent[j] >= 0) {
            j = mParent[j];
        }
        while (x != j) {
            int tmp = mParent[x];
            mParent[x] = j;
            x = tmp;
        }
        return j;
    }

    public void union(int root1, int root2) {
        root1 = find(root1);
        root2 = find(root2);
        if (root1 != root2) {
            mParent[root1] += mParent[root2];
            mParent[root2] = root1;
        }
    }

    public void weightedUnion(int root1, int root2) {
        root1 = find(root1);
        root2 = find(root2);
        if (root1 != root2) {
            int tmp = mParent[root1] + mParent[root2];
            if (mParent[root2] < mParent[root1]) {
                mParent[root1] = root2;
                mParent[root2] = tmp;
            } else {
                mParent[root2] = root1;
                mParent[root1] = tmp;
            }
        }
    }

    public int sizeOfSubSet(int x) {
        while (mParent[x] >= 0) {
            x = mParent[x];
        }
        return Math.abs(mParent[x]);
    }

    public int numOfSubSets() {
        int num = 0;
        for (int anInt : mParent) {
            if (anInt < 0) {
                num++;
            }
        }
        return num;
    }

    public int parentIndex(int x) {
        return mParent[x];
    }
}